Design a video sharing service

check requirement

Q: So, we're talking about yt?
A: Yes
Q: Yt has a lot of feature, what featrues should we focus on?
A: We can focus on video service about upload/storage/let user watch them.
Q: So, it seems that there are two thing we need to handle, upload a lot of video and hanlde video playback, at massive scale.

Try to do myself

For a simple solution

    User -> Decoing Service cluster -> Storage 
                                    -> Database

At first, we need to consider about this task is upload video, we want it can hanlde all flow about upload video, and use check sum for each chunk to check if it have uploaded

User -> divide video to serveral chunk -> decoding service cluster -> cahce service 
            -> storage 
            -> database

Then we need to consider about video plackback

User -> CDN (hot point videio) -> service -> database -> storage service

about storage service, we need to consider about backup, and high capacity, S3 is a good solution.

about database -> we can store meta data for video.

    video id, video name, s3 key, video tag, relation chunck..
    video id, chunk check sum..

course example

we can start on user experience
user will see some data about video

    video name
    video shortcut
    video author
    video ads
    .... client what to display.

user -> web service-> video medata data(noSql)

Then we can consider about where videos come from

cdn -> transacoded videos(distributed object storage, i.e. Google Cloud Storgae

Because CDB is very expansive, we need to do something to reduce the fee.

CDN    ->  transacoded videos
Direct ->

For the strategy to choose the hot video, we need to have a ML modeo to predict it.
about user tag/time/..etc
beside that location is also a good choice that let us choose the cdn

That's talk about how to upload vieio

video metadata -> raw video -> queue -> transconding fleet -> transcoded video

Then we can let it more perfect

user -> loadbalance -> video metadata / raw video 
    -> queue servie -> transcoding fleet
                        |                 |
                      ML model     transcoded video
                        |
                       CDN

Need to improve

For the huge problem, I need to consider from user experence, then can make the disgn more clear and simple.

Same Tree

Q: https://leetcode.com/problems/same-tree/description/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Design Add and Search Words Data Structure

Q: https://leetcode.com/problems/design-add-and-search-words-data-structure/

class Node {
    Node[] childs;
    boolean isTail;

    public Node() {
        this.childs = new Node[26];
    }
}
class WordDictionary {
    Node root = new Node();

    public WordDictionary() {
        
    }
    
    public void addWord(String word) {
        Node now = root;
        for(int i = 0;i < word.length();i++) {
            if (now.childs[word.charAt(i) - 'a'] == null) {
                now.childs[word.charAt(i) - 'a'] = new Node();
            }
            now = now.childs[word.charAt(i) - 'a'];
        }
        now.isTail = true;
    }
    
    public boolean search(String word) {
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        for (int i = 0;i < word.length();i++) {
            List<Node> toSearchNode = new ArrayList<>();
            while(!q.isEmpty()) {
                toSearchNode.add(q.poll());
            }
            if (toSearchNode.size() == 0) {
                return false;
            }
            char c = word.charAt(i);
            for (Node n : toSearchNode) {
                if (c == '.') {
                    for (int j = 0;j < 26;j++) {
                        if (n.childs[j] != null) {
                            q.offer(n.childs[j]);
                        }
                    }
                } else {
                    if (n.childs[c - 'a'] != null) {
                        q.offer(n.childs[c - 'a']);
                    }
                }
            }
        }
        while(!q.isEmpty()) {
            Node now = q.poll();
            if (now.isTail) {
                return true;
            }
        }
        return false;
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

Flatten Binary Tree to Linked List

Q: https://leetcode.com/problems/flatten-binary-tree-to-linked-list/description/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if (null == root) {
            return;
        }
        TreeNode right = root.right;
        root.right = root.left;
        root.left = null;
        flatten(root.right);
        flatten(right);
        TreeNode p = root;
        while(p.right != null) {
            p = p.right;
        }
        p.right = right;
    }
}

Basic Calculator

Q: https://leetcode.com/problems/basic-calculator/

class Solution {
    public int calculate(String s) {

        Stack<Integer> stack = new Stack<Integer>();
        int operand = 0;
        int result = 0; 
        int sign = 1; 
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {
                operand = 10 * operand + (int) (ch - '0');
            } else if (ch == '+') {
                result += sign * operand;
                sign = 1;
                operand = 0;
            } else if (ch == '-') {
                result += sign * operand;
                sign = -1;
                operand = 0;
            } else if (ch == '(') {
                stack.push(result);
                stack.push(sign);
                sign = 1;
                result = 0;
            } else if (ch == ')') {
                result += sign * operand;
                result *= stack.pop();
                result += stack.pop();
                operand = 0;
            }
        }
        return result + (sign * operand);
    }
}